package com.xk._03真题骗._06二叉树;

import com.xk._03真题骗._00bean.TreeNode;

/*
 * @description: https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
 * @author: xu
 * @date: 2022/11/4 16:44
 */
public class _236二叉树的最近公共祖先 {
    /*
    * 以root为根节点的二叉树中查找p、q的最近公共祖先
    *   1. 如果p、q如果同时存在于这棵二叉树中，就能成功返回它们的最近公共祖先
    *   2. 如果p、q都不存在于这棵二叉树中，返回null
    *   3. 如果只有p存在于这棵二叉树中，返回p
    *   4. 如果只有q存在于这棵二叉树中，返回q
    * */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;
        // 以root.left为根节点的二叉树中查找p、q的最近公共祖先
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        // 以root.right为根节点的二叉树中查找p、q的最近公共祖先
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) return root;
        return left == null ? right : left;
    }
}
